package nk;

/**
 * NC99 多叉树的直径
 */
public class NK99_MultipleTreeDiameters {

    public class Interval {
        int start;
        int end;
    }

    /**
     * 树的直径
     *
     * @param n          int整型 树的节点个数
     * @param Tree_edge  Interval类一维数组 树的边
     * @param Edge_value int整型一维数组 边的权值
     * @return int整型
     */
    public int solve(int n, Interval[] Tree_edge, int[] Edge_value) {
        // 方法2 从任意一个节点出发dfs，是直径的一端，再从这一端出发dfs找到另一端
        Info dfs = dfs(Tree_edge, Edge_value, new boolean[n], Tree_edge[0].start);
        return dfs(Tree_edge, Edge_value, new boolean[n], dfs.node).distinct;
    }

    // 需返回节点和距离
    public Info dfs(Interval[] Tree_edge, int[] Edge_value, boolean[] visit, int cur) {
        int max = 0;
        int weight;
        visit[cur] = true;
        Info info = new Info(cur, 0);
        for (int i = 0; i < Tree_edge.length; i++) {
            int start = Tree_edge[i].start;
            int end = Tree_edge[i].end;
            if (start == cur && !visit[end]) {
                Info dfsInfo = dfs(Tree_edge, Edge_value, visit, end);
                weight = Edge_value[i] + dfsInfo.distinct;
                if (max < weight) {
                    max = weight;
                    info.node = dfsInfo.node;
                    info.distinct = weight;
                }
            } else if (end == cur && !visit[start]) {
                Info dfsInfo = dfs(Tree_edge, Edge_value, visit, start);
                weight = Edge_value[i] + dfsInfo.distinct;
                if (max < weight) {
                    max = weight;
                    info.node = dfsInfo.node;
                    info.distinct = weight;
                }
            }
        }
        return info;
    }

    class Info {
        public int node;
        public int distinct;

        public Info(int node, int distinct) {
            this.node = node;
            this.distinct = distinct;
        }
    }

    // ---------------------------------------------------------------

//    public int solve1(int n, Interval[] Tree_edge, int[] Edge_value) {
//        // write code here
//        // 方法1 遍历所有节点去获取其的距离
//        int ans = 0;
//        for (int i = 0; i < n; i++) {
//            ans = Math.max(ans, dfs(Tree_edge, Edge_value, new boolean[n], i));
//        }
//        return ans;
//    }
//
//
//    public int dfs1(Interval[] Tree_edge, int[] Edge_value, boolean[] visit, int cur) {
//        int weight;
//        int max = 0;
//        visit[cur] = true;
//        for (int i = 0; i < Tree_edge.length; i++) {
//            int start = Tree_edge[i].start;
//            int end = Tree_edge[i].end;
//            if (start == cur && !visit[end]) {
//                weight = Edge_value[i] + dfs(Tree_edge, Edge_value, visit, end);
//                max = Math.max(max, weight);
//            } else if (end == cur && !visit[start]) {
//                weight = Edge_value[i] + dfs(Tree_edge, Edge_value, visit, start);
//                max = Math.max(max, weight);
//            }
//        }
//        return max;
//    }

}
